python 数据结构之图的储存方式 |
您所在的位置：网站首页 › python 图 数据结构 › python 数据结构之图的储存方式 |
python 数据结构之图的储存方式
|
参考链接：https://blog.csdn.net/u014281392/article/details/79120406 所描述的图的结构为：
下面介绍不同的储存方式，我想不必详细分别是每个名称都是那种数据来存储的，或是一种，或是两种的组合，这不是再通用的规定约束而来的结果，只是列举了一些灵活的组合而已。 1.邻接集合邻接集合就是把顶点的邻接点放在一个集合中 # 将节点的编号赋值给相应的节点，方便操作 a, b, c, d, e, f, g, h = range(8) N = [{'b', 'c', 'd', 'e', 'f'}, {'c', 'e'}, {'d'}, {'e'}, {'f'}, {'c', 'g', 'h'}, {'f', 'h'}, {'f', 'g'}] 列表中每个集合是每个节点邻接点集 在python2.7中，set([1,3])这样表示，set()表示空集合． 在python3之后的版中，set{1,3}表示集合，空集合仍用set()表示．#查看ａ的邻接节点有哪些 N[a] {'b', 'c', 'd', 'e', 'f'} # 检查g是否为a的一个邻接节点 'g' in N[a] False # 节点a的度 len(N[a]) 5 2.邻接列表 数据结构和邻接集合差不多，唯一的不同是用列表来储存 # 表示同一个图 a, b, c, d, e, f, g, h = range(8) N = [ ['b', 'c', 'd', 'e', 'f'], ['c', 'e'], ['d'], ['e'], ['f'], ['c', 'g', 'h'], ['f', 'h'], ['f', 'g'] ] # 邻接列表表示图结构，与邻接集合的操作相同3.邻接字典 临界字典与前面两个的不同之处在于，其不仅采用字典来储存，字典是键值对，键值对中的value用来表示边的权值这一信息，能表示出与邻居节点之间的关联性 a, b, c, d, e, f, g, h = range(8) N = [{'b':2, 'c':1, 'd':3, 'e':9, 'f':4}, {'c':4, 'e':3}, {'d':8}, {'e':7}, {'f':5}, {'c':2, 'g':2, 'h':2}, {'f':1, 'h':6}, {'f':9, 'g':8}] #操作 'e' in N[a] True 边的权值 N[a]['c'] 1
4.嵌套字典 不用添加序号了 # 以上三种图的表示，都是使用了list类型 # 下面使用嵌套的字典结构 N = {'a':{'b':2, 'c':1, 'd':3, 'e':9, 'f':4}, 'b':{'c':4, 'e':3}, 'c':{'d':8}, 'd':{'e':7}, 'e':{'f':5}, 'f':{'c':2, 'g':2, 'h':2}, 'g':{'f':1, 'h':6}, 'h':{'f':9, 'g':8}}其他的操作和别的结构相同 # a,e之间链接权值 N['a']['e']４．邻接矩阵 # 邻接矩阵，通过一个二维数组，对应图中的每个节点，使用０，１来表示相关节点是否为当前节点的邻居 # 可以使用嵌套list实现 a, b, c, d, e, f, g, h = range(8) N = [[0, 1, 1, 1, 1, 1, 0, 0], [0, 0, 1, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 1, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 1, 0, 1], [0, 0, 0, 0, 0, 1, 1, 0]] # 检查a, b是否为相邻节点,即检查N[a][b]是否为１ N[a][b] == 1True # c节点的度 sum(N[c]) 扩展邻接矩阵，实现一个没有自循环，对边加权 、无自循环状态，对角线元素全部为０ 、加权，用权值替换真值 、将不存在的边设置一个去穷大的权值(float('inf'))，或None a, b, c, d, e, f, g, h = range(8) inf = float('inf') N = [[ 0, 2, 1, 3, 9, 4, inf, inf], [inf, 0, 4, inf, 3, inf, inf, inf], [inf, inf, 0, 8, inf, inf, inf, inf], [inf, inf, inf, 0, 7, inf, inf, inf], [inf, inf, inf, inf, 0, 5, inf, inf], [inf, inf, 2, inf, inf, 0, 2, 2], [inf, inf, inf, inf, inf, 1, 0, 6], [inf, inf, inf, inf, inf, 9, 8, 0]]# 检查a,b是否互为相邻节点,只要邻接权值不是无穷大 N[a][b] < inf
|
【本文地址】
今日新闻 |
推荐新闻 |